package com.yuw.mysorts;

public class TestDriver2 {

	public static void main(String[] args) {
		quickSort();
	}

	/**
	 * 快速排序
	 * 
	 * @param arr
	 *            排序数组
	 * @param low
	 *            左侧起始位置
	 * @param high
	 *            右侧开始位置
	 */
	private static void quickSort() {
		int[] arr = { 58, 34, 65, 89, 74, 1, 24 };
		System.out.println("快速排序之前：");
		printArr(arr);
		// 调用快速排序算法
		doQuickSort(arr, 0, arr.length - 1);
		System.out.println("快速排序之后：");
		printArr(arr);
	}

	/**
	 * 进行递归每轮的处理
	 * 
	 * @param arr
	 *            处理的数组
	 * @param low
	 *            左侧起始位置
	 * @param high
	 *            右侧起始位置
	 * @return 中间分隔位置
	 */
	private static void doQuickSort(int[] arr, int low, int high) {

		// 递归结束条件
		if (low >= high) {
			// 递归结束
			return;
		}

		// 临时变量
		int ll = low;
		int hh = high;
		// 每轮比较的标准值
		// （1）选取第一个元素作为标准元素，
		int flag = arr[low];

		while (ll < hh) {
			// （2）从数列右边起向左查找第一个比标准元素小的数，将该数和第（1）中标准元素的位置进行交换；
			while (ll < hh && arr[hh] >= flag) {
				hh--;
			}
			// 找到位置会后，进行交换处理
			// 只有找到位置时才进行交换
			arr[ll] = arr[hh];
			// （3）从数列左侧起向右查找第一个比标准元素大的数，将该数和第（2）中标准元素的为值进行交换；
			while (ll < hh && arr[ll] <= flag) {
				ll++;
			}
			// 找到位置会后，进行交换处理
			arr[hh] = arr[ll];
		}

		// 左右交替查找结束之后，将标识变量的值放在最后空余的位置上
		arr[hh] = flag;

		// 进行递归处理
		// 标志变量所在的位置，递归处理标识变量左右两部分
		// hh 或ll变量的值就是表示变量最后所在的位置
		// 递归处理左半部分
		doQuickSort(arr, low, hh - 1);
		// 递归处理右半部分
		doQuickSort(arr, hh + 1, high);

	}

	/**
	 * 打印数组内容
	 * 
	 * @param arr
	 *            被打印的数组
	 */
	private static void printArr(int[] arr) {
		System.out.println("数组内容为：");
		for (int i : arr) {
			System.out.print(" " + i);
		}
		// 换行
		System.out.println();
	}
}
